/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/word-search-ii
   @Language: C++
   @Datetime: 17-03-14 10:51
   */

// Time:  O(m * n * h), h is height of trie
// Space: O(26^h)

class Solution {
private:
	struct TrieNode {
		bool isString = false;
		unordered_map<char, TrieNode*> leaves;

		bool insert(const string &s) {
			TrieNode *p = this;
			for (int i=0; i<s.length(); p=p->leaves[s[i++]])
				if (p->leaves.find(s[i]) == p->leaves.cend())
					p->leaves[s[i]] = new TrieNode;
			if (p->isString) return false;  // already exist
			return p->isString = true;
		}
		~TrieNode() {
			for (auto& kv : leaves)
				if (kv.second) delete kv.second;
		}
	};

	void dfs(vector<vector<char> > &board, int row, int col, TrieNode *tn
			,vector<vector<bool> > &vist, unordered_set<string> &ans,string &str){
		if (row<0 || row>=board.size() || col<0 || col>=board[0].size()
			|| !tn->leaves[board[row][col]] || vist[row][col]) return ;
		str.push_back(board[row][col]);
		vist[row][col] = true;
		tn = tn->leaves[board[row][col]];
		if (tn->isString) ans.insert(str);
		
		dfs(board,row+1,col,tn,vist,ans,str);
		dfs(board,row,col+1,tn,vist,ans,str);
		dfs(board,row-1,col,tn,vist,ans,str);
		dfs(board,row,col-1,tn,vist,ans,str);
		
		str.pop_back();
		vist[row][col] = false;
	}
public:
	/**
	 * @param board: A list of lists of character
	 * @param words: A list of string
	 * @return: A list of string
	 */
	vector<string> wordSearchII(vector<vector<char> > &board, vector<string> &words) {
		if (board.size()<1 || board[0].size()<1) return {};
		int row=board.size(), col=board[0].size();
		TrieNode tn;				// store words
		for (int i=0; i<words.size(); tn.insert(words[i++]));
		vector<vector<bool> > vist(row,vector<bool>(col,false));
		unordered_set<string> ans;	// to duplicate
		string str;
		for (int i=0; i<row; ++i){
			for (int j=0; j<col; ++j)
				dfs(board,i,j,&tn,vist,ans,str);
		}
		return vector<string>(ans.begin(),ans.end());
	}
};
